#
# @lc app=leetcode.cn id=501 lang=python
#
# [501] 二叉搜索树中的众数
#
# https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
#
# algorithms
# Easy (55.84%)
# Likes:    782
# Dislikes: 0
# Total Accepted:    237.3K
# Total Submissions: 425K
# Testcase Example:  '[1,null,2,2]'
#
# 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
# 
# 如果树中有不止一个众数，可以按 任意顺序 返回。
# 
# 假定 BST 满足如下定义：
# 
# 
# 结点左子树中所含节点的值 小于等于 当前节点的值
# 结点右子树中所含节点的值 大于等于 当前节点的值
# 左子树和右子树都是二叉搜索树
# 
# 
# 
# 
# 示例 1：
# 
# 
# 输入：root = [1,null,2,2]
# 输出：[2]
# 
# 
# 示例 2：
# 
# 
# 输入：root = [0]
# 输出：[0]
# 
# 
# 
# 
# 提示：
# 
# 
# 树中节点的数目在范围 [1, 10^4] 内
# -10^5 <= Node.val <= 10^5
# 
# 
# 
# 
# 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
# 
#

# @lc code=start
# Definition for a binary tree node.
class Solution(object):
    def __init__(self):
        self.max_num = 0
        self.current_num = 0
        self.last_node = None
        self.result = []

    def findMode(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        if root is None:
            return []
        self.loop(root)
        return self.result


    def loop(self, node):
        if not node:
            return

        self.loop(node.left)

        if self.last_node is None:
            self.current_num = 1
        elif node.val != self.last_node.val:
            self.current_num = 1
        else:
            self.current_num += 1

        if self.current_num == self.max_num:
            self.result.append(node.val) 

        if self.current_num > self.max_num:
            self.result = [node.val]
            self.max_num = self.current_num
        self.last_node = node

        self.loop(node.right)

# # 若为一般树，使用字典存储
# from collections import defaultdict
# class Solution(object):
#     def __init__(self):
#         self.dist = defaultdict(int)


#     def findMode(self, root):
#         """
#         :type root: Optional[TreeNode]
#         :rtype: List[int]
#         """
#         self.loop(root)
#         result = []
#         max_num = max(self.dist.values())
#         for key, value in self.dist.items():
#             if value == max_num:
#                 result.append(key)
#         return result
        
#     def loop(self, node):
#         if not node:
#             return
#         self.dist[node.val] += 1
#         self.loop(node.left)
#         self.loop(node.right)

